// leetcode14：最长公共前缀
// 1. 编写一个函数来查找字符串数组中的最长公共前缀
// 输入:["flower","flow","flight"]
// 输出"f1"
// 输入:["dog","racecar","car"]
// 输出""
var strs = ["flower","flow","flight"];

var longestCommonPrefix = function (strs) {
    if(strs === null || strs.length === 0) return "";
    let prev = strs[0];
    for(let i = 0;i < strs.length;i ++){
        let j = 0;
        for(; j < prev.length && j < strs[i].length;j ++){
            if(prev.charAt(j) !== strs[i].charAt(j)) break;
        }
        prev = strs[i].substring(0,j);
        if(prev === "") return "";
    }
    return prev;
}


var longestCommonPrefix2 = function (strs) {
    if(strs === null || strs.length === 0) return "";
    if(strs.length === 1) return strs[0];
    let max = 0;
    let min = 0;
    for(let i = 1;i < strs.length;i ++){
        if(strs[min] > strs[i]) min = i;
        if(strs[max] < strs[i]) max = i;
    }
    let minlen = strs[min].length;
    for(let i = 0;i < minlen;i ++){
        if(strs[min][i] !== strs[max][i]) {
            return strs[0].substring(0, i);
        }
    }
    return "";
}


// 分支归并思想
var longestCommonPrefix3 = function(strs){
    if(strs === null || strs.length === 0) return "";
    return ICPrefix(strs);
}
function ICPrefix(arrs){
    let length = arrs.length;
    if(length === 1){
        return arrs[0];
    }
    let mid = Math.floor(length/2);
    let left = arrs.slice(0,mid);
    let right = arrs.slice(mid,length);
    return ICPrefixTwo(ICPrefix(left),ICPrefix(right));
}

function ICPrefixTwo(str1,str2){
    let j = 0;
    for(; j < str1.length && j < str2.length;j ++){
        if(str1.charAt(j) !== str2.charAt(j)) break;
    }
    return str1.substring(0,j);
}
console.log(longestCommonPrefix3(strs));

//还有字典树，自查
